1. Field of the Invention
The invention relates to an arbiter circuit used in a packet exchanger, and more particularly to an arbiter circuit used in a packet exchanger which switches a packet between a specific input port and a specific output port by virtue of packet communication technique such as asynchronous transfer mode (ATM). The invention relates further to a method of carrying out arbitration in such a packet exchanger.
2. Description of the Related Art
FIG. 1 is a block diagram of a conventional packet exchanger.
The illustrated packet exchanger is comprised of input ports 500-1 to 500-n, output ports 501-1 to 501-n, a packet switch 5 which switches a packet between the input ports 500-1 to 500-n and the output ports 501-1 to 501-n, input buffers 7-1 to 7-n temporarily accumulating packets having arrived at the input ports 500-1 to 500-n, an arbiter circuit 6, and input highways 502-1 to 502-n connecting the input buffers 7-1 to 7-n to the packet switch 5.
As illustrated in FIG. 2, the packet switch 5 is designed to turn on or off intersections 50 at each of which transmission lines extending in a grid intersect with each other.
The packet switch 5 illustrated in FIG. 2 is accompanied with a problem that when a plurality of the input ports concurrently transmit packets to a specific output port, packets would make collision with one another, resulting in destruction of data carried by the packets. Accordingly, it is necessary in the packet switch 5 to allow only one input port to transmit a packet to a specific output port at certain timing.
As illustrated in FIG. 1, each of the input buffers 7-1 to 7-n is designed to include an input device 72, an output device 73, and logical queues 71-1 to 71-n in association with the output ports 501-1 to 501-n. The input device 72 accumulates packets having arrived at the input ports 500-1 to 500-n, in a trail in one of the logical queues 71-1 to 71-n in dependence on destination of the queue. The output device 73 takes a packet out of a head of the one of the logical queues 71-1 to 71-n, and transmits the packet to the packet switch 5.
The input buffers 7-1 to 7-n transmit output request signals 600-1 to 600-n to the arbiter circuit 6, respectively. The output request signals 600-1 to 600-n indicate of which output port among the output ports 501-1 to 501-n a packet accumulated in the input buffers 7-1 to 7-n is directed.
The arbiter circuit 6 decides input and output ports between which a packet is to be switched in the packet switch 5 such that the packet does not make collision with other packets. After making such a decision, the arbiter circuit 6 transmits output allowance signals 601-1 to 601-n indicative of the decision, to the input buffers 7-1 to 7-n.
Arbitration algorithm for deciding input and output ports between which a packet is to be switched is suggested, for instance, in “Analysis to scheduling algorithm in input buffer type ATM switch”, Electronic Information Communication Society, B-6-20, 1998 (hereinafter, called “article 1”) or “Analysis to High Capacity Packet Switch”, Electronic Information Communication Society, SSE98-160 (hereinafter, called “article 2”).
In accordance with the algorithm suggested in the article 1, output ports to which a cell accumulated in an input buffer is directed are searched, and one of output ports not yet occupied by any input buffers is selected. Such an output port is selected generally in accordance with the round-robin selection process.
The above-mentioned selection step is carried out for all of input buffers. That is, a basic process in which an output port to which a packet is transmitted from a certain input buffer is selected among output ports not yet occupied by any input buffers is carried out to input buffers in a predetermined order. In general, such a basic process is carried out starting from a smaller identification number of input buffers.
Hereinafter, the above-mentioned step is called input sequential arbitration, and a series of steps for carrying out the above-mentioned basic processes in a predetermined number is called an input sequence.
FIG. 3 is a flow-chart showing steps of carrying out the input sequence in the input sequential arbitration. Hereinbelow is explained the input sequence in the input sequential arbitration, with reference to FIG. 3.
First, an order in input buffers is determined in step S41.
Then, all output ports are caused vacant in step S42.
Then, a variable K is substituted by 0 in step S43.
Then, an output port to which a K-th input buffer transmits a packet is selected among vacant output ports in step S44.
Thereafter, 1 is added to the variable K in step S45.
Then, the variable K is judged whether greater than (N−1) in step S46. If the variable K is not greater than (N−1) (NO in step S46), the steps S44 to S46 are repeated. If the variable K is greater than (N−1) (YES in step S46), the input sequence is finished.
In accordance with the algorithm suggested in the article 2, input buffers accumulating a cell which is to be transmitted to an output port are searched, and one of input buffers not yet receiving an allowance to transmit a packet to any one of output ports is selected. Such an input buffer is selected generally in accordance with the round-robin selection process.
The above-mentioned selection step is carried out for all of output ports. That is, a basic process in which an input buffer to be allowed to transmit a packet to a certain output port is selected among input buffers not having an allowance to transmit a packet is carried out to output buffers in a predetermined order. In general, such a basic process is carried out starting from a smaller identification number of output buffers.
Hereinafter, the above-mentioned step is called output sequential arbitration, and a series of steps for carrying out the above-mentioned basic processes in a predetermined number is called an output sequence.
FIG. 4 is a flow-chart showing steps of carrying out the output sequence in the output sequential arbitration. Hereinbelow is explained the output sequence in the output sequential arbitration, with reference to FIG. 4.
First, an order in output ports is determined in step S51.
Then, all input buffers are caused vacant in step S52.
Then, a variable K is substituted by 0 in step S53.
Then, an input buffer to be allowed to transmit a packet to a K-th output port is selected among vacant input buffers in step S54.
Thereafter, 1 is added to the variable K in step S55.
Then, the variable K is judged whether greater than (N−1) in step S56. If the variable K is not greater than (N−1) (NO in step S56), the steps S54 to S56 are repeated. If the variable K is greater than (N−1) (YES in step S56), the output sequence is finished.
FIG. 5 is a timing chart showing a timing at which the input and output sequences are carried out in the input and output sequential arbitration.
In the conventional arbitration, after an input or output sequence has been started, an allowance for transmitting a packet at a certain time is made. After an input or output sequence has been finished, a next input or output sequence is made start. In order to transmit a packet at a maximum rate corresponding to a line rate, each of the input or output sequences is required to be completed within a unit period of time defined as a period of time necessary for transmitting a packet from an input buffer or a period of time necessary for a packet to pass through a line.
As mentioned earlier, the conventional packet exchanger was required to complete the input or output sequence in a unit period of time. In each of the input and output sequences, the basic process for individual input buffer or output port is carried out for all input buffers and output ports. Hence, the number of the basic processes to be carried out in each of the sequences is increased as the number of ports in the packet exchanger increases.
However, since a unit period of time remains unchanged when packets have the same size and a line rate remains unchanged, a time for carrying out the individual basic process has to be decreased down to 1/X, if the number of ports in the packet exchanger is multiplied by X wherein X is an integer equal to or greater than 2.
Accordingly, if the packet exchanger is designed to have an increased capacity, the arbiter circuit carrying out the arbitration has to be designed to have a process capacity thereof multiplied by X in rate, resulting in a significant increase in fabrication cost.
In addition, even if a plurality of classes classified by its priority, there the conventional packet exchanger does not have an algorithm for efficiently accumulating the classes.
Japanese Unexamined Patent Publication No. 7-297831 has suggested an input buffer type ATM switch circuit including a plurality of input buffers at an input of an ATM switch. In the suggested input buffer type ATM switch circuit, cells are grouped into a plurality of levels in dependence on delay of the cells. Each of the cells stores therein a period of time for which the cell can be stored in the input buffer for each identifiers of the cell.
The suggested circuit is comprised of a plurality of cell queues associated with each of the delay levels, a cell counter counting the number of cells accumulated in the input buffer, first means for generating arbitration data weighed in accordance with the delay levels of the cells, the period of time transmitted from the cell queue, and the number of the cells accumulated in the input buffer, and second means for, if a cell is requested to be directed to the same output port from the input buffers, allowing a cell to be transmitted to the output port from an input buffer which is most heavily weighed in the arbitration data generated by the first means.
Japanese Unexamined Patent Publication No. 10-32585 has suggested an ATM switch controller arranged between an input buffer and an output buffer, including a first circuit which monitors how degree the output buffer is used and transmits a signal indicative of a degree at which the output buffer is used, and a second circuit which arbitrates an output cell supplied to the ATM switch from the input buffer, in accordance with the signal.
Japanese Patent No. 2894442 (Japanese Unexamined Patent Publication No. 11-68779) has suggested a short cell switch having a variable length, which can process a low-rate voice signal in a short period of time. The short cell switch is comprised of predominantly of a hardware.
Japanese Unexamined Patent Publication No. 9-321768 has suggested an ATM exchange including an input buffer temporarily accumulating an ATM cell input through a certain input line, a cross-bar type switch exchanging an ATM cell output from the input buffer, and an arbiter circuit providing conditions for turning on or off the cross-bar type switch, in accordance with priority provided to FIFO in the input buffer. The input buffer includes FIFOs in the number equal to the number of output lines in each of input lines, a distributor distributing cells to FIFO associated with an output line number acquired from header data of the ATM cell, and a selector selecting FIFO from which a cell is to be read out, in accordance with a signal transmitted from the arbiter circuit. The arbiter circuit is comprised of a sub-arbiter circuit determining FIFO having highest priority, based on priority level information of FIFOs in the input lines, a master arbiter circuit carrying out arbitration in competition among the input lines, and an exchange table register in which correspondence between input line numbers and output line numbers is stored.
However, the above-mentioned problems remain unsolved even in the above-mentioned Publications.